<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>动态规划练习01</title>
    </head>
    <body></body>
    <script type="text/javascript">
        /**
            给定一个字符串s和一个字符串t，计算在s的子序列中t出现的个数。

            输入：s = "ra b b b i t", t = "ra b b i t"
            输出：3

            输入：s = " b a b g b a g ", t = " b a g " 
            输出：5
        **/

        /***
            分析：我们使用 dp[i][j] 表示 t的前i个字符可以由s的前j个字符组成的个数
            那么我们就可以得到 
                
                如果我们假设 s 的第 j 个字符和 t 的第 i 个字符相同:

                    我们就可以说： 1. 如果我们使用 s 的第 j 个字符和 t 的第 i 个字符 匹配，
                                    剩下的字符： dp[i-1][j-1]包含了多少种情况，就是我们最终的结果。
                                2.如果我们不使用 s 的第 j 个字符和 t 的第 i 个字符 匹配，
                                    也就是我们 dp[i][j-1] 我们看看j - 1里边包含了多少个 s 的 前 i 个字符

                如果 s 的第 j 个字符和 t 的第 i 个字符不相同:
                    
                    我们就计算 s 的 j - 1 个字符是不是和 t 的第 i 个字符相等



                for(let j = 1; j < s.length; j ++) {
                    if(t.charAt(i - 1) === s.charAt(j - 1)) {
                        dp[i][j] = dp[i-1][j-1] + dp[i][j-1];
                    } else {
                        dp[i][j] = dp[i][j-1];
                    }
                }

                dp[0][j] = 1; // 就是当t = ""
        */

        function numDistinct(s, t) {
            var slen = s.length;
            var tlen = t.length;
            var dp = [];
            for (let i = 0; i <= tlen; i++) {
                dp[i] = [];
                for (let j = 0; j <= slen; j++) {
                    dp[i][j] = 0;
                }
            }

            for (var j = 0; j <= slen; j++) {
                dp[0][j] = 1;
            }

            for (let i = 1; i <= tlen; i++) {
                for (let j = 1; j <= slen; j++) {
                    if (t.charAt(i - 1) === s.charAt(j - 1)) {
                        dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1];
                    } else {
                        dp[i][j] = dp[i][j - 1];
                    }
                }
            }
            console.log(dp);
            return dp[tlen][slen];
        }
        // var s = "rabbbit";
        // var t = "rabbit";

        var s = "babgbag";
        var t = "bag";

        console.log(numDistinct(s, t));
    </script>
</html>
